package com.topInterview;

/**
 * 在排序数组中查找元素的第一个和最后一个位置
 *
 * @Author: huangzhigao
 * @Date: 2022/2/19 17:08
 */
public class Leecode34_findFisrtAndLastNumPosition {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length < 1) {
            return new int[]{-1, -1};
        }

        int left = 0;
        int right = nums.length - 1;
        int index = -1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] == target) {
                index = mid;
                break;
            } else {
                if (nums[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }

        if (index == -1) {
            return new int[]{-1, -1};
        } else {
            int first = index;
            int last = index;
            while (first > -1) {
                if (nums[first] != target) {
                    break;
                }
                first--;
            }

            while (last < nums.length) {
                if (nums[last] != target) {
                    break;
                }
                last++;
            }

            return new int[]{first + 1, last - 1};
        }

    }

    public int[] searchRange2(int[] nums, int target) {
        if (nums == null || nums.length < 1) {
            return new int[]{-1, -1};
        }

        int first = findFirst(nums,target);
        int last = findLast(nums,target);
        return new  int[]{first,last};

    }


    public int findFirst(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                res = mid;
                right = mid - 1;
            }
        }

        return res;
    }


    public int findLast(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                res = mid;
                left = mid + 1;
            }
        }

        return res;
    }

}
